package com.clstu.sort;

/**
 * 比较希尔,快排,基数排序(桶排序),归并排序的速度
 * //由快到慢分别是(规模大的情况下):
 * 测试结果 桶排序------>快速排序------>归并排序----->希尔排序
 */
public class Compare {
    public static void main(String[] args) {
        //测试比较各种比较快的排序算法的速度
        int arrSize = 8000000;
        int[] arr = new int[arrSize];
        int[] arr1 = new int[arrSize];
        int[] arr2 = new int[arrSize];
        int[] arr3 = new int[arrSize];
        int[] tmp = new int[arrSize];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=(int)(Math.random()*80000);
            arr1[i]=arr[i];
            arr2[i]=arr[i];
            arr3[i]=arr[i];
        }
        long start = System.currentTimeMillis();
        ShellSort.shellSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("希尔排序"+arr.length+"个数据耗时:     "+(end-start)+"ms");//1819ms

        start = System.currentTimeMillis();
        QuickSort.quickSort2(arr1,0,arr2.length-1);
        end = System.currentTimeMillis();
        System.out.println("快速排序(左神版)"+arr.length+"个数据耗时:"+(end-start)+"ms");//579ms

        start = System.currentTimeMillis();
        MergeSort.mergeSort(arr2,0,tmp.length-1,tmp);
        end = System.currentTimeMillis();
        System.out.println("归并排序"+arr.length+"个数据耗时:     "+(end-start)+"ms");//891ms

        start = System.currentTimeMillis();
        RadixSort.radixSort(arr3);
        end = System.currentTimeMillis();
        System.out.println("基数排序(桶排序)"+arr.length+"个数据耗时:"+(end-start)+"ms");//371ms

        System.out.println("排序后是否有序:arr:"+isSorted(arr)+" arr1:"+isSorted(arr1)+" arr2:"+isSorted(arr2)+" arr3:"+isSorted(arr3));
    }

    //编写方法判断数组是否已经有序
    public static boolean isSorted(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i]>arr[i+1]) return false;
        }
        return true;
    }
}
